#include <stdio.h>
#include <stdlib.h>

// 定义二叉树节点结构体
typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 创建新节点
TreeNode* createNode(int data) {
    TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

// 在中序遍历中查找根节点的位置
int searchInOrder(int inorder[], int start, int end, int value) {
    for (int i = start; i <= end; i++) {
        if (inorder[i] == value) {
            return i;
        }
    }
    return -1;
}

// 构建二叉树的递归函数
TreeNode* buildTree(int preorder[], int inorder[], int inorderStart, int inorderEnd, int *preorderIndex, int size) {
    printf("当前的中序遍历开始下标为：%d, 结束下标为：%d\n", inorderStart, inorderEnd);
    // 打印当前中序遍历的数组
    for (int i = inorderStart; i <= inorderEnd; i++) {
        printf("%d ", inorder[i]);
    }
    printf("\n");


    if (inorderStart > inorderEnd) {
        return NULL;
    }

    // 取出前序遍历的根节点
    int rootValue = preorder[*preorderIndex];
    printf("当前的前序遍历的根节点值为：%d\n\n", rootValue);
    printf("----------------------------------------------------------------\n\n");
    (*preorderIndex)++;

    // 创建根节点
    TreeNode *root = createNode(rootValue);

    // 在中序遍历中找到根节点的位置
    int inorderIndex = searchInOrder(inorder, inorderStart, inorderEnd, rootValue);

    // 构建左子树和右子树
    root->left = buildTree(preorder, inorder, inorderStart, inorderIndex - 1, preorderIndex, size);
    root->right = buildTree(preorder, inorder, inorderIndex + 1, inorderEnd, preorderIndex, size);

    return root;
}

// 中序遍历二叉树
void printInOrder(TreeNode *root) {
    if (root != NULL) {
        printInOrder(root->left);
        printf("%d ", root->data);
        printInOrder(root->right);
    }
}

// 主函数示例
int main() {
    // 示例前序遍历和中序遍历序列
    int preorder[] = {1, 2, 4, 5, 3, 6, 7};
    int inorder[] = {4, 2, 5, 1, 6, 3, 7};
    int size = sizeof(preorder) / sizeof(preorder[0]);

    int preorderIndex = 0;
    TreeNode *root = buildTree(preorder, inorder, 0, size - 1, &preorderIndex, size);

    // 打印中序遍历结果以验证
    printf("中序遍历结果: ");
    printInOrder(root);
    printf("\n");

    // 释放内存（略）

    return 0;
}
